#include <stdio.h>//inclued for printf
#include <stdlib.h>//included for malloc
#include <string.h>//included for strcpy, strlen

#include "board.h"

/**
 * Created by: Sam Olmsted
 * Last edit: Sam 
 *
 * This file defines all things related to boards. 
 **/ 

/**
 * By: Sam Olmsted
 * defines a stone. 
 **/
typedef struct{
  int column;
  int row;
} stone;

/**
 * By: Sam 
 * defines a group of stones. 
 **/
typedef struct{
  stone** stones;
  int size; 
} group;


int findDeadGroup(board* myBoard, group* dead, stone* stone, char color);
int hasBeenChecked(group * dead, stone* stone);
void updateBoard(board* myBoard, group* dead, char opponent);
void appendCaptureMessage(char* message, int sizeOfMessage, 
                          int capture_white, int capture_black);
void check(myBoard* myBoard char opponent, int row, int column,
    int *atariflag, int *capflag);

/** Verified by Sam Olmsted 4/24/12 By Jon and Jeff 4/27/12
 * size is a constent defined in board.h
 * Prints out the board indicated by b
 *[stdout:=stdout + size lines each containing a row of b's position array
 *     with a space between each element + a line containing b's message.]
 */
void printBoard(board* b)
{
    /** -1 */
    int CHAR_PER_ELEMENT=2;
    int CHAR_PER_LINE=size*CHAR_PER_ELEMENT;
    char string[size*CHAR_PER_LINE+1];//the one is for the \0 character
    int i=0;
    int j=0;
    /** -2 */
    string[size*CHAR_PER_LINE]='\0';
    /** -3
     *[string[0 up to 162]:=size lines each containing a row of b's
      *    position array with a space between each element + "\n"]
     */
    for(i=0; i<size; i++)
    {
        /** -3.1
         *[string[i*CHAR_PER_LINE through (i+1)*CHAR_PER_LINE-1]:= a line
         *     containing a row of b's position array with a space between
         *     each element]
         */
         for(j=0; j<CHAR_PER_LINE; j+=CHAR_PER_ELEMENT)
         {
            /** -3.1.1 */
            string[i*CHAR_PER_LINE+j*CHAR_PER_ELEMENT]=b->position[i][j];
            string[i*CHAR_PER_LINE+j*CHAR_PER_ELEMENT+1]=' ';
         }
         /** -3.2 */
         string[(i+1)*CHAR_PER_LINE-1]='\n';
    }
    /** -4
     *[stdout:=stdout + string + b->message + '\n']
     */
    printf("%s%s\n", string, b->message);
}

/**Verified by Sam Olmsted 4/24/12
 * new version varified by Jon and Jeff 4/27/12
 * 
 * Creates a copy of the board indicated by b
 *[*clone:=copy of *b
 * return clone
 */
board* copyBoard(board* b)
{
    /*-1
     *[*clone:=allocated space
     * clone:=pointer to *clone]
     */
    board* clone= (board*) malloc(sizeof(board));
    /*-2
     *[memory pointed at by clone:= memory pointed at by b for size of
     *     board]
     */
    memcpy(clone, b, sizeof(board));
    /*-3
     * 4-3-2012 - Sam 
     * this should not copy string, just add a blank string 
     *[memory pointed at by clone->message:= memory pointed at by
     *     b->message for size of that message]
     */
    clone->message= (char*) malloc(sizeof(char));
    /*-4
     * 4-3-2012 - Sam 
     * changed strcopy to just adding a null termination.
     *[clone->message:=b->message
     * return clone]
     */
     *(clone->message) = '\0';
     return(clone);
}

/**
 * Sam Olmsted
 * 4-2-2012
 * Create a new board. See header for IF.
 **/
board* createBoard(){
  /**
   * --1
   * Setup the board. 
   * [ *myBoard   := create space for board 
   *    i        := 0 ]
   **/
   board* myBoard= (board*) malloc(sizeof(board));
   int i = 0;

   /**
    * --2
    * The message is not set to Null so no checks need to be made
    * from the printBoard. The message can be realloced if more 
    * space is needed and should not be replaced. 
    * [ *message := null termination ]
    **/
   char* message = (char*) malloc(sizeof(char));
   *message = '\0';

   /**
    * --3
    * Add nine empty rows to the board. Each row will have nine empty 
    * spaces to it.
    * [ position := a 9x9 board of empty spaces  ]
    **/  
    for(i; i<9; i++){
      /**
       * --3 body
       * Add an empty row to the board. 
       * position[i] := an empty row
       **/

      /**
       * --3.2
       * Put blank spaces into the row. 
       * [ position[i][j] := an empty board spaces  ]
       **/
      for(j=0; j<9; j++){
        /**
         * --3.2 body 
         * Add in the empty board spaces. 
         * [ row[j] = an empty space  ]
         **/

         /**
          * --3.2.1
          * Add an empty space to the board
          * [ position[i][j] = an empty space  ]
          **/
         board->position[i][j] = '.';
      }
    }

  /**
   * --4
   * Add the default values into board.
   * [  board->message      := message
   *    board->capture_white := 0
   *    board->capture_black := 0  ]
   **/
  board->message = message;
  board->capture_white = 0;
  board->capture_black = 0;

  return board;
}

/**
 * Sam Olmsted
 * 4-2-2012
 * Make a move on the board and pass back relevent messages
 *  [ see header  ]
 **/
void move(board* myBoard int column, int row, char color){
  /**
   * --1 */
  char* message = board->message;
  char opponent = 'o';
  int isAtari   = 0;
  int isCapture = 0;

  /**
   * --2 
   * Set the color of the opponent to use to collect dead stones. 
   * [  if color is white -> 
   *      opponent := black
   *    else -> 
   *      opponent := white ]
   **/
  if(color == 'o'){
    opponent = '#';
  }

  /**
   * --4
   * place stone 
   * [ board := next board  ]
   **/
  board[column][row] = color;

  /**
   * --5
   * Update the board using Go rules.
   * [  check the north stone -> 
   *      if there is an atari or isAtari is set -> 
   *        isAtari := 1
   *      else ->
   *        I
   *      if there is a capture or isCapture is set-> 
   *        isCapture := 1
   *        board     := and updated board without the captured stones  ]
   *      else ->
   *        I
   **/

  check(myBoard opponent, column+1, row, &isAtari, &isCapture);
  /**
   * --6
   * Update the board using Go rules.
   *    check the south stone -> 
   *      if there is an atari or isAtari is set -> 
   *        isAtari := 1
   *      else ->
   *        I 
   *      if there is a capture or isCapture is set-> 
   *        isCapture := 1
   *        board     := and updated board without the captured stones  ]
   *      else ->
   *        I
   **/
  check(myBoard opponent, column-1, row, &isAtari, &isCapture);

  /**
   * --7
   * Update the board using Go rules.
   *    check the east stone -> 
   *      if there is an atari or isAtari is set -> 
   *        isAtari := 1
   *      else ->
   *        I
   *      if there is a capture or isCapture is set-> 
   *        isCapture := 0
   *        board     := and updated board without the captured stones ]
   *      else ->
   *        I
   **/
  check(myBoard opponent, column, row+1, &isAtari, &isCapture); 

  /**
   * --8
   * Update the board using Go rules.
   *    check the west stone -> 
   *      if there is an atari or isAtari is set -> 
   *        isAtari := 1
   *      else ->
   *        isAtari := 0
   *      if there is a capture or isCapture is set-> 
   *        isCapture := 0
   *        board     := and updated board without the captured stones  ]
   *      else ->
   *        I
   **/
  check(myBoard opponent, column, row-1, &isAtari, &isCapture); 


  /*--9
   *[if isAtari==1 and isCpture==1->
   *     board->message:=a message that stones are in atari and stones were
   *         captured
   * elseif isAtari==1
   *     board->message:=a message that stones are in atari
   * elseif isCapture==1
   *     board->message:=a message that stones were captured
   * else->I   
   **/
  if( isAtari && isCapture ){
    /*-9.1.1
     *[board->message:=a message that stones are in atari]
     */
    message = (char*) realloc(message, 7*sizeof(char));
    *message = "Atari\n\0";
    /*-9.1.2
     *[board->message:=board + a message that stones are in atari]
     */
    appendCaptureMessage(message, 7, board->capture_white, board->capture_black);
    
  } else if( isAtari ){
    /*-9.2
     *[board->message:=a message that stones are in atari]
     */
    message = (char*) realloc(message, 6*sizeof(char));
    *message = "Atari\0";

  } else if( isCapture ){
    /*-9.1.2
     *[board->message:=a message that stones are in atari]
     */
    appendCaptureMessage(message, 7, board->capture_white, board->capture_black);
  }
}

/**
 * Privat Methods
 * TODO: add at top of the file 
 **/

/**
 * Edited: Sam and Cedric 
 * This function returns dead or alive. The return values are: 
 * Alive: 1 >   
 * Dead: 0
 * [  dead :=  the group of stones that stone is a part of
 *    return number of liberties that group has]
 **/
int findDeadGroup(board* myBoard group* dead, stone* stone, char color){
  /**
   * --1
   * [position := the value of the place on the board
   *  isDead:=0]
   **/
  char position = board[stone->column][stone->row];
  int isDead=0;
  stone *next;

  /**
   * --2 
   * Check to see if the given square is free. Put this check first so you don't
   * loose track of pointers. 
   * [  if the place on the board has already been searched -> 
   *      return 0
   *    else -> I ]
   **/
  if( hasBeenChecked(dead, stone) ){
    free(stone);
    return 0
  } 
  /*-3
   *[*dead:=*dead + stone
   * dead->size:=size+1]
   */
  dead->stones = (stone*) realloc(dead->stone, ((dead->size)+1)*sizeof(stone));
  dead->stones[dead->size] = stone;
  dead->size++;

  /**
   * --4
   * Check to see if the given square is free
   * [  if position is free -> 
   *      return 0
   *    else -> I ]
   **/
  if( position == '.' ){
    return 1;
  }

  
  /**
   * --5
   * Check to see if the give square is the other color 
   * [  if position is free -> 
   *      return 2
   *    else -> I ]
   **/
  if( position != color ){
    return 0
  }
  /*-6
   *[if there is space to the north of stone
   *     next:=neighbor space to the north
   *     dead:=the group of stones that next is a part of
   *     isDead+:=number of liberties that group has]
   */
  if( stone->column > 0 ){
    next=malloc(sizeof(stone));
    next->row=stone->row;
    next->column=ston->column-1;
    isDead+=findDeadGroup(myBoard dead, next, color)
  }
  /*-7
   *[if there is space to the south of stone
   *     next:=neighbor space to the south
   *     dead:=the group of stones that next is a part of
   *     isDead+:=number of liberties that group has]
   */
  if( stone->column < size-1 ){
    next=malloc(sizeof(stone));
    next->row=stone->row;
    next->column=ston->column+1;
    isDead+=findDeadGroup(myBoard dead, next, color)
  }
  /*-8
   *[if there is space to the west of stone
   *     next:=neighbor space to the west
   *     dead:=the group of stones that next is a part of
   *     isDead+:=number of liberties that group has]
   */
  if( stone->row > 0 ){
    next=malloc(sizeof(stone));
    next->row=stone->row-1;
    next->column=ston->column;
    isDead+=findDeadGroup(myBoard dead, next, color)
  }
  /*-9
   *[if there is space to the east of stone
   *     next:=neighbor space to the east
   *     dead:=the group of stones that next is a part of
   *     isDead+:=number of liberties that group has]
   */
  if( stone->row < size-1 ){
    next=malloc(sizeof(stone));
    next->row=stone->row+1;
    next->column=ston->column;
    isDead+=findDeadGroup(myBoard dead, next, color)
  }
  /*-10*/
  return isDead;
}

/**
 * Check to see if a given stone is in the dead group. The return values:
 * Exists: 1
 * Does not exists: 0
 *[if stone is in dead->
 *     return 1
 * else->
 *     return 0 
 **/ 
int hasBeenChecked(group * dead, stone* stone){
  /*--1*/
  int i=0;
  int searchColumn;
  int searchRow;

  /*--2 
   *[if stone is in dead->
   *     return 1
   * else->I
   */
  for(i; i<dead->size; i++){
    /*--2 body 
     *[if stone==dead->stones[i]
     *     return 1
     * else->I
     */

    /*--2.1*/
    searchColumn = dead->stones[i]->column;
    searchRow    = dead->stones[i]->row;
    
    /**
     * --2.2
     * Check to see of there is a stone that shares the same column and row 
     * number as one in the dead group.
     * [  if position matches a given stone in dead->stones[i]-> 
     *      return 1
     *    else -> I ]
     **/
    if( searchColumn == stone->column && searchRow == stone-> stone->row ){
      return 1;
    }
  }

  /*--3*/
  return 0;
}

/**
 * This function updates the board by removing dead stones.
 *[if dead group is white ->
 *     board->capture_white+:=dead->size
 * else->
 *     board->capture_black+:=dead->size
 * in either case
 *     board:=board with locations indicatated by dead set to be empty
 *         space]
 **/
void updateBoard(board* myBoard, group* dead, char opponent)
{
    /*-1
     *[if dead group is white ->
     *     board->capture_white+:=dead->size
     * else->
     *     board->capture_black+:=dead->size
     */
    if(opponent=='o')
    {
        board->capture_wighte+=dead->size;
    }
    else
    {
        board->caputre_black+=dead->size;
    }
    /*-2
     *[board:=board with locations indicated by dead set to be empty
     *     space]
     */
    for(i; i<dead->size; i++){
        /*-2 body
         *[board:=board with locations indicated by dead->stones[i] set to
         *     be empty space]
         */
        board[dead->stones[i]->column][dead->stones[i]->row] = '.';
    }
}

/**
 * Created by: Sam Olmsted
 * 4-3-2012
 * Creates the captured string message. 
 * [  message := message + "\nwhite captured: {total white captures}\n"
 *               "total black captures: {black captures}\n\0" ]
 **/
void appendCaptureMessage(char* message, int sizeOfMessage, 
                          int capture_white, int capture_black){

  /**
   * --1
   * Strings of the number of captures for white and black 
   * [ whiteString := the string of number of captures
   *   blackString := the string of number of captures  ]
   **/
  char* whiteString = atoi(capture_wight); 
  char* blackString = atoi(capture_black); 

  /**
   * --2 
   * Figure out the size of the message string. The needed space for the 
   * words "white captures: \n " is 17. Hence need to add an extra 34 and 
   * one for the null, so 35.
   * [  size := the size of the new string  ]
   **/
  int size = sizeOfMessage + strlen(whiteString) + strlen(blackString)+35;

  /**
   * --3
   * Make room in the string. 
   * [ message := space for the new message ]
   **/
  message = (char*) realloc(message, size*sizeof(char));

  /**
   * concate the strings together. 
   * [  message := message + "\nwhite captured: {total white captures}\n"
   *               "total black captures: {black captures}\n\0" ]
   **/
   strcat(message, "white captures:");
   strcat(message, whiteString);
   strcat(message, "\n");
   strcat(message, "black captures:");
   strcat(message, blackString);
   strcat(message, "\n");
}

/**
 * Given a stone, specified by row and column, check to see if it's group
 * is in Atari. 
 * 
 *[If the stone's group is in atari->
 *     atariflag:=1;
 * else->I
 * if that group is captuered->
 *     capflag:=1;
 *     board->capture_wight+=number of captuered wight stones
 *     board->capture_black+=number of captuered black stones
 * else->I  ]
 **/
void check(board * myBoard char opponent, int row, int column,
           int *atariflag, int *capflag){
    int libs;
    /**
     * --1
     *[*dead, *stone:=allocated space
     * dead:=pointer to *dead
     * stone:=pointer to *stone     
     **/
    dead  = (group*) malloc(sizeof(group));
    stone = (stone*) malloc(sizeof(stone));

    /*--2*/
    stone.column  = column; 
    stone.row     = row;
    dead->stones  = stone;
    dead.size     = 1;
    
    /*--3
     *[dead:=the group of stones that stone is a part of
     * libs:=number of liberties that group has]
     */
    libs = findDeadGroup(myBoard dead, stone, opponent);

    /*-4
     *[if libs==0->
     *     board:=board with captuerd stones removed and captuers
     *         incramented by the number of those stones
     *     capflag:=1;
     * else if libs==1->
     *     atariflag:=1;
     * else->I
     */
    if(libs==0)
    {
        /*-4.1
         * Remove the dead stones from the board.
         * [  if the dead group is white ->
         *    board->capture_white+=dead->size
         * else->
         *     board->capture_black+=dead->size
         * in either case
         *     board:=board with locations indicatated by dead now as an 
         *            empty space.  ]
         */
        updateBoard(myBoard dead, opponent);
        *capflag=1;
    }
    else if(libs==1)
    {
        /*-4.2*/
        *atariflag=1;
    }

    /**
     * --5
     * Free up the stones used to find the dead group.
     * [ dead->stones := dealloced  ]
     **/
    for(int i=0; i<dead.size; i++){
      /*-5 Body 
       * [dead->stones[i]:=dealloced]
       **/
      free(dead->stones[i]);
    }

    /*-6
     *[dead:=dealloced]
     */
    free(dead);
} 
